package sword_offer;

import common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName _34pathSumInTreeNode
 * @Description: 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 *
 * 叶子节点 是指没有子节点的节点。
 *
 *  
 *
 * 示例 1：
 *
 *
 *
 * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
 * 输出：[[5,4,11,2],[5,8,4,5]]
 * 示例 2：
 *
 *
 *
 * 输入：root = [1,2,3], targetSum = 5
 * 输出：[]
 * 示例 3：
 *
 * 输入：root = [1,2], targetSum = 0
 * 输出：[]
 *  
 *
 * 提示：
 *
 * 树中节点总数在范围 [0, 5000] 内
 * -1000 <= Node.val <= 1000
 * -1000 <= targetSum <= 1000
 * 注意：本题与主站 113 题相同：https://leetcode-cn.com/problems/path-sum-ii/
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: yongliang.ma
 * @Create_time:2022/10/13 10:18
 */
public class _34pathSumInTreeNode {

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> output = new ArrayList<>();
        if (root == null)// 由于节点可为null，所以判断下 有的测试用例中包含
            return result;
        output.add(root.val);
        dfs(root, result, output, target - root.val);

        return result;
    }

    public void dfs(TreeNode treeNode, List<List<Integer>> result, List<Integer> output, int rest){
        // 剪枝
        if (treeNode == null)
            return;

        // 为叶子节点且rest恰好满足
        if (treeNode.left == null && treeNode.right == null && rest == 0){
            result.add(new ArrayList<>(output));
            return;
        }

        // 左节点 下一层，回溯状态
        if (treeNode.left != null){
            output.add(treeNode.left.val);
            dfs(treeNode.left, result, output, rest - treeNode.left.val);
            output.remove(output.size() - 1);
        }

        // 右节点，下一层，回溯状态
        if (treeNode.right != null){
            output.add(treeNode.right.val);
            dfs(treeNode.right, result, output, rest - treeNode.right.val);
            output.remove(output.size() - 1);
        }
    }
}
